Convolutional codes provide forward error correction for second and third generation wireless communications. In forward error correction the transmitter transmits redundant data. The receiver recovers from any errors in transmission using the redundant data. Forward error correction contrasts with systems where the receiver checks for errors and signals for retransmission. In forward error correction no such retransmission is needed or requested. Forward error correction is also used in satellites, modems, digital radios and television set-top boxes.
Viterbi decoders are commonly used to decode the coded information in forward error correction systems. FIG. 1 illustrates the two main functional parts of a prior art Viterbi decoding circuit. State metric unit 101 computes state metrics from input branch metrics. The resulting hard decisions are stored in random access memory (RAM) 102. Traceback unit 103 uses the hard decisions stored in RAM 102 to traverse the trellis in reverse order and obtain the decoded bits.
Viterbi decoders have two main parts state metric generation and traceback. If the traceback is not initialized correctly, then the traceback results can fail. This results in poor bit error rate (BER).
FIG. 2 illustrates the construction of an example state metric unit 101. State metric unit 101 generates 2k−1 hard decisions, where k is the constraint length. The constraint length k is equal to the number of bits in the encoder that influence the output bits. State metric unit 101 is based on a cascade architecture that provides an area efficient and flexible design. State metric unit 101 consists of three component types: ACS units 201, 203, 206 and 209; transpose units 202, 205 and 208; and pretraceback units 204, 207 and 210. The connections between these units are shown in FIG. 2.
The cascade architecture of FIG. 2 supports trellis sizes from 16 to 256 states or constraint lengths k from 5 to 9. State metric unit 101 performs 4 ACS operations and 3 transpose operations. Each block receives 2 state metrics as inputs and forms 2 state metrics and outputs. Each ACS unit 201, 203, 206 and 209 calculates the state metrics for one trellis stage. Therefore, the 4 ACS units calculate the state metrics for 4 consecutive trellis stages.
The ordering of the specific states within each trellis stage is important. The ordering is such that the calculated data can flow from block to block keeping all units as busy as possible. There are 2k−1 states for each trellis stage. Using matrix equations it is possible to keep track of the states as they pass through each block. The matrix equations will be in the form of a 2k−2 by 2 matrix. For example:
      [                            a                          b                                      c                          d                                      e                          f                                      g                          h                      ]     This architecture supports radix 16 trellises. For trellis sizes 16 and 256, the architecture can be fully pipelined. For other trellis sizes, the units are not 100% utilized. This requires introduction of holes in the pipeline. The holes are introduced by turning the various blocks off with the enable signals as illustrated in FIG. 2. Table 1 lists activation of each of the units of FIG. 2.
TABLE 1Num-berPassofNum-ACS1T1x4ACS2T1x2ACS3T1x1ACS4stateber2012022032052062082092561ONONONONONONON2562ONONONONONONON1281ONONONONONONON1282OFFOFFONONONONON641ONONONONONONON642OFFOFFOFFOFFONONON321ONONONONONONON322OFFOFFOFFOFFOFFOFFON161ONONONONONONONThe ON label indicates that the functional block is performing as desired. The OFF label indicates that the functional block is merely passing the data through the block. The pipelining remains constant and is not affected by the blocks activation level.
The term ACS stands for Add, Compare and Select. FIG. 3 illustrates a functional diagram of ACS units 201, 203, 206 and 209 of FIG. 2. The equations for each ACS unit are:SI=max(SA+BM, SB−BM); andSJ=max(SA−BM, SB+BM).This computation is illustrated schematically in FIG. 3. Each ACS unit also generates two decision bits as follows:DI=0 when (SA+BM)>(SB−BM), else DI=1; andDJ=0 when (SA−BM)>(SB+BM), else DJ=1.
Transpose units 202, 205 and 208 perform matrix transpose operations on the incoming states. FIG. 4 illustrates the 1 by 1 transpose operation of transpose unit 208. FIG. 5 illustrates the 1 by 2 transpose operation of transpose unit 205. FIG. 6 illustrates the 1 by 4 transpose operation of transpose unit 202.
State metric unit 101 performs the first part of traceback with a register exchange structure as shown in FIG. 2. Cross switches 204, 207 and 210 allow the previously generated decision bits to either stay in their respective rail or cross over to the opposite rail depending on the decision bits from corresponding ACS units. FIG. 7 illustrates cross switches 204, 207 and 210 divided into 2 smaller blocks for additional detail. In the first block 701 input Tx determines which y input is supplied to a first y+1 output. In the second block 702 input Bx determines which y input is supplied to a second y+1 output. The current decision bits are appended to the outputs of each cross switch.
State metric unit 101 cascade structure outputs two 4-bit partial traceback words for each rail. These 8 bits are packed in 32-bit register 801 (see FIG. 8). When register 801 is full, the 32-bit data is stored in hard decision RAM 102.
The traceback function traverses the trellis in reverse order. Using the previously stored decisions as a guide, traceback unit 103 selects the maximum likelihood path through each trellis section. Each path corresponds to a decoded decision bit. The traceback function is divided into two steps pretraceback and traceback. Pretraceback groups the decoded decision bits into groups of 4 bits. The actual number of bits depends on k and the pass number. Traceback unit 103 performs the second part of the traceback as illustrated in FIG. 8. This part traces backwards through the data. Traceback unit 103 is able to traverse up to four trellis stages at a time due to the pretraceback results. This produces up to four decision bits at a time.
State index shift register 810 contains k−1 elements. Four traceback bits selected by select unit 821 are stored in state index shift register 810 while a set of bits are output. The output bits are used to generate the lower portion of the address for hard decision RAM 102 via concatenater 822. The upper portion of the address comes from multiplexer 823. Multiplexer 823 selects either the decision state counter specifying the address for storing data from register 801 at input D or the traceback counter specifying the address for recalling data at output Q.
Traceback unit 103 works with several constraint lengths from 5 to 9. State metric unit 101 generates a different number of bits depending on the pass number. This is listed in Table 2.
TABLE 2HD RAMValid bitsValid bitsaddresseskfor pass 1for pass 2per pass9443284316742864145442For example, if the constraint length k is 8, then the number of valid bits output from the state metric unit is 4, 3, 4, 3, . . . 4, 3. To simplify the hardware all accesses are treated as four bits. The last column in Table 2 lists the number of hard decision (HD) RAM 103 addresses used per pass.
FIG. 9 illustrates an expanded logic diagram of traceback unit 103 with more details of registers and required multiplexers. State index shift register 810 is divided into two 4-bit registers 811 and 813. Register 811 stores 4 bits high order bits which are labeled state-hi. Register 813 stores the 4 bit low order bits labeled state_lo.
At the start of the traceback state-hi register 811 is initialized with 4 bits from the fmaxi signal as selected by multiplexer 831. Fmaxi is the starting state index for the traceback. Fmaxi[k−2:k−5] is the last trellis stage with the highest value determined by state metric unit 101. The lower order bits of fmaxi[3:0] initialize state-lo register 813 via multiplexer 832.
During traceback, multiplexer 832 for the LSB addresses for hard decision RAM 102 are listed in column 3 of Table 3. The 32-bit data read from hard decision RAM 102 is grouped into eight 4-bit pretraceback sections. The contents of the state-lo[2:0] register 813 labeled s-mux1 selects one of those eight 4-bit sections via multiplexer 821. These 4-bits labeled q4 are loaded into state-hi register 811 as shown in FIG. 9.
TABLE 3Hard DecisionHard DecisionPassRAM 102 LSBRAM 102 DatakNumberAddressIndex91 or 2state_hi[3:0] &state_lo[2:0]state_lo[3]81state_hi[3:0]state_lo[2:0]82state_hi[2:0] &state_lo[2:0]state_lo[3]71state_hi[3:1]state_lo[2:0]72state_hi[1:0] &state_hi[0] &state_lo[3]state_lo[2:0]61state_hi[3:2]state_lo[2:0]62state_hi[0] &state_hi[1:0] &state_lo[3]state_lo[0]51state_hi[3]state_lo[2:0]
The initialization of state-hi register 811 and state-lo regiester 813 is based on the value of the fmaxi signal. The data stored in the hard decision RAM 102 is grouped into 4-bit groups from the pretraceback units. If either the value of fmaxi or the data stored in hard decision RAM 102is incorrect, then traceback unit 103 will be incorrectly initialized. This will result in either an incorrect starting address for hard decision RAM 102, incorrect data being read from hard decision RAM 102 or an incorrect multiplexer selection signal s-mux1 of the 32-bit output data from hard decision RAM 102. Any one of these three errors will result in an incorrect data for that group of bits from the pretraceback unit. The incorrect data will result in many failing trellis stages until traceback unit 103 recovers. This leads to a worse BER. This is a serious problem because the main goal of forward error correction (FEC) is to improve the BER.